package algorithmTopics.link;

import java.util.HashMap;
import java.util.Map;

/**
 * 缓存  有待更新，此方法不对
 *
 * @author 86155
 * @date 2025/07/12
 */
class LRUCache {

    static class KeyLink {
        Integer key;
        //下一个
        KeyLink next;
        //上一个
        KeyLink pre;


        public KeyLink(Integer key) {
            this.key = key;
        }
    }

    private int capacity;

    /**
     * 最老
     */
    private KeyLink oldest;
    /**
     * 最新
     */
    private KeyLink latest;

    private Map<Integer, Integer> map;


    /**
     * 放置链表对象 ,更新缓存用
     */
    private Map<Integer, KeyLink> set;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        set = new HashMap<>(capacity);
    }

    public int get(int key) {
        // 返回值
        Integer v = map.getOrDefault(key, -1);
        // 更新缓存时间
        if (v != -1) {
            //更新缓存
            update(this.set.get(key));
        }
        return v;
    }

    public void put(int key, int value) {

        // 加入
        if (this.capacity > 0 || set.containsKey(key)) {
            map.put(key, value);
            // 更新并放入 缓存
            addAndFlash(key);
            this.capacity--;
        } else  {
            // 丢弃最旧数据 容量已经满了
            deleteOldest();
            //放入最新数据
            put(key,value);
        }


    }

    private void deleteOldest() {
        this.capacity++;
        this.map.remove(this.oldest.key);
        this.set.remove(this.oldest.key);
        //说明是最后一个
        if (this.oldest.pre == null) {
            this.latest = null;
            this.oldest = null;
        } else {
            this.oldest.pre.next = null;
            this.oldest = this.oldest.pre;
        }

    }

    /**
     * 添加和更新缓存
     *
     * @param key 钥匙
     */
    private void addAndFlash(int key) {
        if (set.get(key) != null) {
            // 不用添加 新的缓存 更新就行
            KeyLink keyLink = set.get(key);
            update(keyLink);
        } else {
            KeyLink keyLink = new KeyLink(key);
            set.put(key, keyLink);
            //初始化
            this.latest = this.latest == null ? keyLink : this.latest;
            this.oldest = this.oldest == null ? keyLink : this.oldest;
            update(keyLink);
        }

    }

    /**
     * 更新缓存位置
     *
     * @param keyLink 关键环节
     */
    private void update(KeyLink keyLink) {
        if (latest == keyLink) {
            return;
        }
        //看看是否已经有这个缓存
        // 更新老缓存
        //看看是否是最旧
        if (keyLink == oldest) {
            this.oldest = keyLink.pre == null ? keyLink : keyLink.pre;
        }
        //之前的最新
        KeyLink top = this.latest;
        // 更新最新
        this.latest = keyLink;

        //是不是第一次加入
        if (keyLink.pre != null) {
            // 取出 双向链表 next pre 都需要更新
            keyLink.pre.next = keyLink.next;

        }
        if (keyLink.next != null) {
            keyLink.next.pre = keyLink.pre;
        }
        //放置在头部
        keyLink.next = top;
        keyLink.pre = null;

        top.pre = keyLink;


    }
}